package arithmetic_40;

import java.util.Arrays;

/**
 *
 * @author wxh
 */
public class Solution_8 {

	public int coinChange(int[] coins, int amount) {

		// dp[i]定义为：组合成i元面值，最少需要多少个硬币
		int[] dp = new int[amount + 1];
		// 初始化每个金额为最少需要amount+1个硬币（先初始化到最大值）
		Arrays.fill(dp, amount + 1);

		dp[0] = 0;
		for (int i = 1; i <= amount; i++) {
			for (int j = 0; j < coins.length; j++) {
				if (coins[j] <= i) { // 面值要比当前i小
					dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1); //
				}
			}
		}
		return dp[amount] > amount ? -1 : dp[amount];
	}

}